<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 1. 力扣 654
      // 构造最大二叉树
      // 伪代码
      function constructMaxTree(arr) {
        if (arr.length == 0) return null;
        // 找出最大值所在索引
        var maxIndex = 0;
        for (var i = 0; i < arr.length; i++) {
          if (arr[i] > arr[maxIndex]) {
            maxIndex = i;
          }
        }

        var root = new Tree(arr[maxIndex]);
        root.left = constructMaxTree(arr.slice(0, maxIndex));
        root.right = constructMaxTree(arr.slice(maxIndex + 1));
        return root;
      }

      // 通过前序和中序遍历构造二叉树
      // preorder = [3,9,20,15,7]
      // inorder = [9,3,15,20,7]
      // 找出两者之间分布规律
      // 从前序遍历获知3是根节点,中序遍历得知左子树[9],右子树[15,20,7]
      // 递归 构建左子树和 右子树即可
      // 力扣105

      function buildTree(preorder, inorder) {
        return build(preorder, inorder);
      }
      function build(preorder, inorder) {
        if (preorder.length == 0) {
          return null;
        }
        var rootVal = preorder[0];

        var idx = inorder.indexOf(rootVal);
        var inleft = inorder.slice(0, idx);
        var leftlen = inleft.length;
        var preleft = preorder.slice(1, 1 + leftlen);
        var inright = inorder.slice(idx + 1);
        var preright = preorder.slice(1 + leftlen);
        var root = new TreeNode(rootVal);
        root.left = build(preleft, inleft);
        root.right = build(preright, inright);
        return root;
      }

      // 通过中序和后序遍历 还原二叉树

      // inorder = [9,3,15,20,7]
      // postorder = [9,15,7,20,3]
      // 找规律
      // 从后序遍历获知3是根节点, 中序遍历得知左子树[9], 右子树[(15, 20, 7)];
      // 力扣106
    </script>
  </body>
</html>
